1. Field of the Invention
The present invention relates generally to a method for processing of pixels of an image segment by a computer, and in particular for signal extrapolation of brightness values and/or color values of pixels of a first image segment onto pixels of a second image segment, and to an apparatus for practicing the method.
2. Description of the Related Art
The coding of video signals in accordance with, for example, the picture coding standards H.261, H.263, MPEG1 and MPEG2 is frequently based on a block-oriented discrete cosine transform (DCT). However, these block-oriented image coding methods are not suitable for image coding methods which are not based on rectangular blocks but rather in which, for example, objects are segmented from an image and the image segments are coded. These methods are referred to as region-based or object-based image coding methods. In this case, digital images are segmented in a manner corresponding to the objects appearing in the scene. Separate coding of these segmented objects is carried out instead of the coding of picture blocks as in the case of block-based image coding methods. In this case, the coding is usually effected by modeling of the segmented objects and subsequent transmission of the modeling parameters of these segmented objects.
After the image information has been transmitted from a transmitter to a receiver, the individual objects of the image are reconstructed again in the receiver using the modeling parameters that have been transmitted.
One possibility for modeling the objects consists in a series expansion of the image function in accordance with a set of suitably selected base functions. The modeling parameters then correspond to the expansion coefficients of this image function. Such image modeling is the foundation of transform coding. If the intention is to code individual image objects having any desired boundary, a transformation for segments having any desired boundary (as a rule not convex) is necessary.
Two fundamental approaches have existed hitherto for such a transformation.
In the method which is described in the publication by M. Gilge, T. Engelhardt and R. Mehlan, Coding of arbitrarily shaped image segments based on a generalized orthogonal transform, Signal Processing: Image Communication 1, pp. 153-180, October 1989, the given image segment is first of all embedded in a circumscribing rectangle having the smallest possible dimensioning. For this rectangle it is possible to specify a discrete cosine transform (DCT) which is completely specified by the base functions of the transformation. In order to adapt this transformation to the segment shape, the base functions defined on the rectangle are successively orthogonalized with regard to the shape of the segment. The resulting orthogonal, shape-dependent base functions then form the segment-adapted transformation sought.
One disadvantage of this solution approach may be seen in the fact that the implementation of this method requires a great deal of computing power and of memory space. Furthermore, this known method has the disadvantage that reliable statements cannot be made about the suitability of the resulting transformation for the purpose of data compression since the transformation essentially depends on the orthogonalization sequence, and thus on the specific implementation of the method.
The publication by T. Sikora and Bxc3xa9la Makai, Shape-adaptive DCT for generic coding of video, IEEE Trans. Circuits and Systems for Video Technology 5, pp. 59-62, February 1995 describes a method in which the given image segment is transformed separately according to rows and columns. For this purpose, all the lines of the image segment are first of all aligned on the left and successively subjected to a one-dimensional horizontal transformation whose transformation length corresponds in each case to the number of pixels in the corresponding line. The resulting coefficients are then transformed a further time in the vertical direction.
This method conceals the disadvantage, in particular, that the correlations of the brightness values of the pixels (similarities of the pixels) cannot be completely utilized on account of the resorting of the pixels.
In order to improve this method disclosed in the two publications T. Sikora and Bxc3xa9la Makai, Shape-adaptive DCT for generic coding of video, IEEE Trans. Circuits and Systems for Video Technology 5, pp. 59-62, February 1995, and T. Sikora, S. Bauer and Bxc3xa9la Makai, Efficiency of shape-adaptive 2-D transforms for coding of arbitrary shaped image segments, IEEE Trans. Circuits and Systems for Video Technology 5, pp. 254-258, June 1995, describes a method in which a transformation for convex image segment shapes which is adapted for a simple image model is carried out. In this case, however, the only image segment shapes that are permitted are those which have no interruptions (holes) on traversing rows or columns.
The known methods described above furthermore have the disadvantage that owing to the variable transformation length, standard transformation methods and/or standard modules cannot be employed for carrying out the transformation.
Furthermore, I. Donescu et al., A Comparison of Efficient Methods for the Coding of Arbitrarily Shaped Image Segments, Proceedings of Picture Coding Symposium, Melbourne, pp. 13.-15.3. 1996, pp. 181-186, 1996, discloses assigning a predetermined, fixed brightness value to all the pixels of a square image segment with 8xc3x978 pixels which do not belong to a first image segment which is at least partly contained in the square image segment.
This method primarily has two disadvantages.
Firstly, in the boundary region of the first image segment and the square image segment, it is possible for discontinuities of the signal profile of the brightness values to occur between pixels, thereby causing high-frequency spectral components, which leads to an undesirable and unnecessary, increased coding complexity and hence requirement for transmission capacity.
Secondly, this method is restricted to block-based methods with image segments having a square shape.
Since the standard image transformation methods cannot be employed, the methods disclosed in the publications M. Gilge, T. Engelhardt and R. Mehlan, Coding of arbitrarily shaped image segments based on a generalized orthogonal transform, Signal Processing: Image Communication 1, pp. 153-180, October 1989; T. Sikora and Bxc3xa9la Makai, Shape-adaptive DCT for generic coding of video, IEEE Trans. Circuits and Systems for Video Technology 5, pp. 59-62, February 1995; T. Sikora, S. Bauer and Bxc3xa9la Makai, Efficiency of shape-adaptive 2-D transforms for coding of arbitrary shaped image segments, IEEE Trans. Circuits and Systems for Video Technology 5, pp. 254-258, June 1995, incur considerable costs for encoding units which use the known methods described above.
Standard image transformation methods are disclosed in R. J. Clarke: Transform Coding of Images, Academic Press, London, pp. 72-134, 1985.
German Patent Document DE 41 36 636 A1 discloses a device for coding video signals which is used to implement signal extrapolation of a signal profile from a first picture area into a second picture area. The signal extrapolation is effected by mirroring the signal profile at d of the edge of the first picture area.
The publication by J.-R. Ohm, Digitale Bildcodierung [Digital ImageCoding], Springer, Berlin, ISBN 3-540-58579-6 pp. 32-49, 1995, demonstrates various possibilities for signal extrapolation: a periodic continuation, a symmetrical continuation and also a value-constant continuation of the signal profile.
All the methods disclosed in German Patent Document DE 41 36 636 A1 and the publication by J.-R. Ohm, Digitale Bildcodierung [Digital ImageCoding], Springer, Berlin, ISBN 3-540-58579-6 pp. 32-49, 1995, have the underlying disadvantage that in the event of a spectral transformation onto the entire signal, resulting from the signal profile and the extrapolated signal profile, an undesirably high number of high spectral components are produced and, consequently, a large number of spectral coefficients in the higher spectral domain arise, which must additionally be coded and transmitted.
ConsequentIy, the invention is based on the problem of providing a method for the processing of pixels of an image segment of any desired shape which has, as a result, image segments of an image-segment target shape, it being the case that in the image segments of the image-segment target shape, the signal profile of the brightness values and/or of the color values has, on the one hand, a smooth profile in the region which does not lie in the original image segment, and, on the other hand, has as far as possible no discontinuities in the signal profile in a boundary region between the original image segment and the region which does not lie in the original image segment.
The problem is solved by the method or the processing of pixels of a first image segment, which has any desired shape, by a computer, in which the pixels of the first image segment are assigned a brightness value and/or a color value, the brightness values and/or the color values are extrapolated onto pixels of a second image segment, which has any desired shape, the extrapolation is carried out in such a way that a signal profile of the brightness values and/or of the color values of the pixels of the second image segment is smoothed, and the extrapolation is carried out in such a way that the signal profile of the brightness values and/or of the color values of the pixels of the second image segment is adapted to the brightness values and/or to the color values of the pixels of the first image segment in a boundary region between the first image segment and the second image segment.
In the method, the pixels of a first image segment are assigned a brightness value and/or a color value, it being possible for the first image segment to have any desired shape. The brightness values and/or color values are extrapolated onto pixels of a second image segment likewise having any desired shape. In the course of the extrapolation, it is ensured that the signal profile of the brightness values and/or of the color values of the pixels in the second image segment is smoothed. Furthermore, the extrapolation is carried out in such a way that in a transition region of pixels of the first image segment and pixels of the second image segment, as far as possible no discontinuities occur in the signal profile of the brightness values and/or color values. This means that the boundary region between the first image segment and the second image segment is likewise smoothed during the extrapolation.
The method enables the signal profile of brightness values and/or color values of pixels of a first image segment to be extrapolated onto pixels of a second image segment, high spatial frequencies in the signal profiles and hence high spectral components and thus spectral coefficients for higher frequencies being avoided as far as possible. This leads to a reduction of spectral coefficients that usually have to be quantized, coded and transmitted. Consequently, a considerable saving is achieved in the quantization, coding and transmission of spectral coefficients in the coding of images.
Advantageous developments of the invention emerge from from a method in which a digital filter having a smoothing characteristic is used for the extrapolation. Preferably, the extrapolation of the brightness values and/or of the color values of the pixels of the second image segment is carried out on the basis of pixels of the second image segment which are adjacent to the pixels of the first image segment. A local mean value filter is used as the digital filter. Alternately, a median filter is used as the digital filter. The brightness values and/or the color values of the pixels of the second image segment may be initialized with a predeterminable value at the beginning of the method. The predeterminable value is produced from the one mean value of the brightness values and/or of the color values of the pixels of the first image segment.
Preferably, the method is carried out a number of times. For example, the method is carried out until, after an iteration, a sum of changes of at least some of the brightness values and/or of the color values of the pixels of the second image segment in comparison with at least one preceding iteration is less than a predeterminable first threshold value. Alternately, the method is carried out until, after an iteration, a mean value of changes of at least some of the brightness values and/or of the color values of the pixels of the second image segment in comparison with at least one preceding iteration is less than a predeterminable second threshold value. As a further alternative, the method is carried out until, after an iteration, a sum of changes of at least some of the brightness values and/or of the color values of the pixels of the second image segment in comparison with at least one preceding iteration is less than a preterminable third threshold value.
For the extrapolation, the first function is formed which has at least one first term and one second term, the first term is used to ensure that the signal profile of the brightness values and/or of the color values of the pixels of the first image segment is preserved as far as possible, the second term is used to ensure that the signal profile of the brightness values and/or of the color values of the pixels of the second image segment is smoothed, and the second term is used to ensure that the signal profile of the brightness values and/or of the color values of the pixels of the second image segment is adapted to the brightness values and/or to the color values of the pixels of the first image segment in a boundary region between the first image segment and the second image segment. The first term is determined from a difference between the signal profile of the brightness values and/or of the color values of the pixels of the first image segment and a signal profile supplemented onto the brightness values and/or the color values of the pixels of the second image segment. The second term is at least produced from any desired differentiation of a signal profile supplemented onto the brightness values and/or the color values of the pixels of the second image segment. The second term is at least produced from a second differentiation of the signal profile supplemented onto the brightness values and/or the color values of the pixels of the second image segment.
In this method, the supplemented signal profile is transformed into the spectral domain, the transformed, supplemented signal profile having spectral coefficients, an intermediate function is formed by inserting the transformed, supplemented signal profile) into the first function, a linear equation system is formed in that the intermediate function is differentiated with respect to the respective spectral coefficients and is set to be equal to zero, values of the spectral coefficients are determined by solving the linear equation system for the spectral coefficients.
Integer arithmetic may be used in the method. In one embodiment, the first image segment and the second image segment together have a square shape. The present method may be used in the context of transform encoding. Alternately, it is used in the context of a discrete cosine transform. As yet another alternative, it is used in the context of a wavelet transform. Further, it may be used in the context of a sub-band transform.
The present invention also provides an apparatus for the processing of pixels of a first image segment, which has any desired shape, having a computing unit which is set up in such a way that the pixels of the first image segment are assigned a brightness value and/or a color value, the brightness values and/or the color values are extrapolated onto pixels of a second image segment, which has any desired shape, the extrapolation is carried out in such a way that a signal profile of the brightness values and/or of the color values of the pixels of the second image segment is smoothed, and the extrapolation is carried out in such a way that the signal profile of the brightness values and/or the color values of the pixels of the second image segment is adapted to the brightness values and/or to the color values of the pixels of the first image segment in a boundary region between the first image segment and the second image segment.
The apparatus computing unit is set up in such a way that a digital filter having a smoothing characteristic is used for the extrapolation. Preferably, the computing unit is set up in such a way that the extrapolation of the brightness values and/or of the color values of the pixels of the second image segment is carried out on the basis of pixels of the second image segment which are adjacent to the pixels of the first image segment. A local mean value filter is used as the digital filter according to the invention, or a median filter is used as the digital filter instead.
In a preferred arrangment, the computing unit is set up in such a way that for the extrapolation, a first function is formed which has at least one first term and one second term, the first term is used to ensure that the signal profile of the brightness values and/or of the color values of the pixels of the first image segment is preserved as far as possible, the second term is used to ensure that the signal profile of the brightness values and/or of the color values of the pixels of the second image segment is smoothed, and the second term is used to ensure that the signal profile of the brightness values and/or of the color values of the pixels of the second image segment is adapted to the brightness values and/or to the color values of the pixels of the first image segment in a boundary region between the first image segment and the second image segment.
This computing unit is set up in such a way that the first term is determined from a difference between the signal profile of the brightness values and/or of the color values of the pixels of the first image segment and a signal profile supplemented onto the brightness values and/or the color values of the pixels of the second image segment. The second term is at least produced from any desired differentiation of a signal profile is supplemented onto the brightness values and/or the color values of the pixels of the second image segment. The second term is at least produced from a second differentiation of the signal profile supplemented onto the brightness values and/or the color values of the pixels of the second image segment.
In one example, the computing unit is set up in such a way that the supplemented signal profile is transformed into the spectral domain, the transformed, supplemented signal profile having spectral coefficients, an intermediate function is formed by inserting the transformed, supplemented signal profile into the first function, a linear equation system is formed in that the intermediate function is differentiated with respect to the respective spectral coefficients and is set to be equal to zero, and values of the spectral coefficients are determined by solving the linear equation system for the spectral coefficients.
Specific features of the invention provide that integer arithmetic is used in the method. The first image segment and the second image segment together have a square shape. The apparatus is used in the context of transform encoding, or in the context of a discrete cosine transform, or in the context of a wavelet transform, or in the context of a subband transform.
It is advantageous to use a digital filter having a smoothing characteristic for the extrapolation of the signal profile, in order to ensure the requirements for smoothing the signal profile. In this development of the method, the extrapolation of the signal profile is carried out completely in the space domain.
Furthermore, it is advantageous to use a local mean value filter as the digital filter, since optimum extrapolation with regard to the smoothing criteria is achieved by the mean value filter.
Moreover, it is advantageous to initialize the brightness values and/or color values of the pixels of the second image segment at the beginning of the method with a value, for example with the mean value of the brightness values and/or of the color values of the pixels of the first image segment. The result of the method is improved further in this way.
Furthermore, it is advantageous to carry out the method in a plurality of iterations, the smoothing properties thereby being improved further.
However, the method need not necessarily be carried out exclusively in the space domain; a variant is likewise provided in which a first function is formed which is composed at least of a first term and a second term, which are used to ensure, on the one hand, the criterion of faithfulness to the original of the first image segment and, on the other hand, the smoothness criteria during the extrapolation of the brightness values and/or of the color values.
Moreover, in a development of the method, it is advantageous, proceeding from a generally assumed function which describes the supplemented signal profile in the second image segment, in the method to transform this function into the spectral domain, insert the transformed function into the first function and to minimize the first function. The resultant linear equation system is solved for the spectral coefficients, and the corresponding spectral coefficients are quantized, coded and transmitted.
The development of the method in which integer arithmetic is used achieves a considerable saving of computation time and of outlay on hardware for the implementation of the method.
Furthermore, it is advantageous for the first image segment and the second image segment together to have a square shape. This enables standardized, block-based image coding methods, for example the DCT, and the existent, optimized hardware modules and software realizations to be used. This means that standard modules for block-based transform coding can be used in the context of this method for any desired first image segments, after the implementation of this method. This leads to a considerable cost saving in the case of so-called object-based image coding as well.